How Quantum Computers Will Correct Their Errors
The state of a single quantum bit needs to be imprinted on nine quantum bits for the error correction to work.
Samuel Velasco/Quanta Magazine
Introduction
In 1994, Peter Shor, a mathematician then at Bell Labs in New Jersey, proved that a quantum computer would have the power to solve some problems exponentially faster than a classical machine. The question was: Could one be built? Skeptics argued that quantum states were too delicate — the environment would inevitably jumble the information in the quantum computer, making it not quantum at all.
A year later, Shor responded. Classical error-correcting schemes measured individual bits to check for errors, but that approach wouldn’t work for quantum bits, or “qubits,” since any measurement would destroy the quantum state, and hence the calculation. Shor figured out a way to detect whether an error had occurred without measuring the state of the qubit itself. Shor’s code marked the beginning of the field of quantum error correction.
The field has flourished. Most physicists see it as the only path to building a commandingly powerful quantum computer. “We won’t be able to scale up quantum computers to the degree that they can solve really hard problems without it,” said John Preskill, a physicist at the California Institute of Technology.
As with quantum computing in general, it’s one thing to develop an error-correcting code, and quite another to implement it in a working machine. But at the beginning of October, researchers led by Chris Monroe, a physicist at the University of Maryland, reported that they had demonstrated many of the ingredients necessary to run an error-corrected circuit like Shor’s.
So how did Shor crack the conundrums he faced? He used the added complexity of quantum mechanics to his advantage.
Repeat Repeat Repeat
Shor modeled his protocol after the classical repeater code, which involves making copies of each bit of information, then periodically checking those copies against each other. If one of the bits is different from the others, the computer can correct the error and continue the calculation.
Shor designed a quantum version of this. He used three individual “physical” qubits to encode a single qubit of information — the “logical” qubit. Shor’s quantum repeater code couldn’t be exactly the same as the classical version, though. The essential power of quantum computation comes from the fact that qubits can exist in a “superposition” of being in a combination of 0 and 1 at the same time. Since measuring a quantum state would destroy the superposition, there wasn’t a straightforward way to check to see whether an error had occurred.
Instead, he found a way to tell if the three physical qubits were in the same state as one another. If one of the qubits was different, it would indicate that an error had occurred.
The task is not unlike solving a simple logic puzzle. You’re given three balls that look identical, but one of the balls might have a different weight. You also have a simple balance scale. What measurements will let you determine whether there is an oddball in the mix, and if so, which one it is?
Samuel Velasco/Quanta Magazine
The answer is to first pick two balls and compare their weights, then replace one of the balls with the remaining ball and check again. If the scale was balanced both times, then all balls are identical. If it was balanced only once, then one of the replaced balls is the odd one out. If the scales are imbalanced both times, the ball that stayed still is the culprit.
Shor’s code replaces the scales with two extra “ancilla” qubits. The first of these compares the first and second physical qubits; the other compares the second and third. By measuring the states of these ancillary qubits, you learn if the three information-containing qubits are in identical states without disturbing the state of any of them.
This code protects against a bit flip, which is the only possible error that can occur in classical computing. But qubits have one more potential source of error.
Superpositions are the key to quantum computing, but it’s not just the value of the qubit that’s important. The relative “phase” between qubits matters too. You can think of this phase as a wave — it tells you the location of the wave’s peaks and troughs. When two waves are in phase, their ripples are synchronized. If they collide, they will constructively interfere, merging into a single wave double the size. But if the waves are out of phase, then when one wave is at its peak, the other is at its nadir, and they will cancel each other out.
A quantum algorithm takes advantage of this phase relationship among its qubits. It sets up a situation where the correct answer to a calculation constructively interferes and is therefore amplified, while the incorrect answer gets suppressed by destructive interference.
But if an error causes the phase to flip, then destructive interference can switch to constructive interference, and the quantum computer will start amplifying the wrong answer.
Shor found that he could correct for phase errors using a similar principle to the one he used for bit flips. Each logical qubit gets encoded into three qubits, and ancilla qubits check to see if one of the phases has flipped.
Shor then combined the two codes. The result was a code that translated one logical qubit into nine physical qubits that offered both bit and phase checks.
Tolerant to a Fault
Shor’s code would in principle protect a single logical qubit from errors. But what if there was a mistake in the error measurements themselves? Then, in your attempt to correct the nonexistent error, you would flip a bit and unwittingly introduce a real error. In some cases, this could cause a cascade of errors to propagate through the code.
Shor’s code also didn’t consider how he would operate a quantum computer built from his logical qubits. “We need some way to do computations on the encoded states, without losing that protection. And that’s not straightforward,” said Daniel Gottesman, a theoretical computer scientist at the University of Maryland.
So in 1996, his third consecutive year of blazing trails, Shor came up with the notion of fault tolerance. A fault-tolerant code can deal with errors introduced by the environment, by imperfect operations on those qubits, and even by the error-correction steps themselves — provided the rate at which these errors occur is below a certain threshold.
Last month, Monroe and his group announced that they had used a fault-protected version of Shor’s code called the Bacon-Shor code to demonstrate nearly all the tools necessary for a fully fault-tolerant quantum computer. They encoded a logical qubit into the quantum states of nine ions, then, using four ancilla qubits, they showed that they could fault-tolerantly perform all single-qubit operations necessary for quantum computing. The result shows that a fault-tolerant quantum computer is possible.
This goal remains distant, though. Monroe thinks the advantage granted by error correction won’t be seen until quantum computers have reached about 100 logical qubits. Such a machine would require about 1,300 physical qubits, since each logical qubit needs nine physical qubits plus four ancillas. (The current largest quantum processor, IBM’s newly announced Eagle, has 127 physical qubits.) At that point, “we’re going to start making a qubit factory and then we’ll introduce error correction,” said Monroe. “But not before.”
